Tương tự với các biểu thức số, một xâu Fibonacci được định nghĩa đệ quy như sau:

F n := F ( n ) := { b khi  n = 0 ; a khi  n = 1 ; F ( n − 1 ) + F ( n − 2 ) khi  n > 1. {\displaystyle F_{n}:=F(n):={\begin{cases}b&{\mbox{khi }}n=0;\\a&{\mbox{khi }}n=1;\\F(n-1)+F(n-2)&{\mbox{khi }}n>1.\\\end{cases}}} ,

trong đó dấu "+" ký hiệu cho phép ghép hai xâu. Dãy các xâu Fibonacci khởi đầu là:

b, a, ab, aba, abaab, abaababa, abaababaabaab, …

Độ dài của mỗi xâu Fibonacci chính là số Fibonacci, và có một xâu Fibonacci tương ứng với mỗi số Fibonacci.

Các xâu Fibonacci cung cấp dữ liệu vào cho các minh dụ cho một vài thuật toán máy tính.